/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._1287;

/**
 * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
 *
 * 请你找到并返回这个整数
 *
 *  
 *
 * 示例：
 *
 * 输入：arr = [1,2,2,6,6,6,6,7,10]
 * 输出：6
 *  
 *
 * 提示：
 *
 * 1 <= arr.length <= 10^4
 * 0 <= arr[i] <= 10^5
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._1287
 * @ClassName: ElementAppearing
 * @Author: linyaonan
 * @Date: 2020/1/9 10:06
 */
public class ElementAppearing {
    public int findSpecialInteger(int[] arr) {
        int l = arr.length;
        int maxCount= 1;
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max == arr[i]) {
                maxCount++;
                if (maxCount / (double) l > 0.25) {
                    return max;
                }
            } else {
                max = arr[i];
                maxCount = 1;
            }
        }
        return max;
    }
}
